package stru1.day13;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringJoiner;

/**
 * 700. 二叉搜索树中的搜索
 */
public class Solution1 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(7));
        print(searchBST(root, 2));
        print(searchBST(root, 5));
    }

    /**
     * 递归
     */
    public static TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;
        else if (root.val > val) return searchBST(root.left, val);
        else return searchBST(root.right, val);
    }

    private static void print(TreeNode node) {
        StringJoiner sj = new StringJoiner(",", "[", "]");
        if (node == null) {
            System.out.println(sj);
            return;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(node);
        if (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            sj.add(String.valueOf(curr.val));
            if (curr.left != null) stack.push(curr.left);
            if (curr.right != null) stack.push(curr.right);
        }
        System.out.println(sj);
    }
}
